﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


// 1、三角形最小路径和
//
//给定一个三角形 triangle ，找出自顶向下的最小路径和。
//
//每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
//也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。


class Solution
{
public:
    int minimumTotal(vector<vector<int>>& triangle)
    {

        for (int i = triangle.size() - 1; i >= 0; --i)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (i < triangle.size() - 1)
                {
                    triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
                }
            }
        }

        return triangle[0][0];
    }
};


// 2、2 的幂
//
//给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
//
//如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。


class Solution
{
public:
    bool isPowerOfTwo(int n)
    {
        return n > 0 && (n & (n - 1)) == 0;
    }
};



// 3、位1的个数
//
//编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。


class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int ret = 0;
        for (int i = 0; i < 32; ++i)
        {
            if (n & (1 << i))
            {
                ret++;
            }
        }

        return ret;
    }
};



// 4、颠倒二进制位
//
//颠倒给定的 32 位无符号整数的二进制位。


class Solution
{
public:
    uint32_t reverseBits(uint32_t n)
    {
        uint32_t rev = 0;

        for (int i = 0; i < 32 && n > 0; ++i)
        {
            rev |= (n & 1) << (31 - i);
            n >>= 1;
        }

        return rev;
    }
};



// 5、只出现一次的数字
//
//给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//
//你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间



class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        // n ^ 0 = n
        // n ^ n = 0
        int ret = 0;

        for (int i = 0; i < nums.size(); ++i)
        {
            ret ^= nums[i];
        }

        return ret;
    }
};